package Top101K;

/**
 * @Author quan
 * @Description 合并两个排序链表
 * @Date 2023/12/5 12:17
 */
public class BM4_Merge {
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        // 边界条件：如果有一个链表为空，直接返回另一个链表
        if(pHead1 == null){
            return pHead2;
        }
        if(pHead2 == null){
            return pHead1;
        }
        // 1-定义3个指针，分别从两个子链表的头部开始遍历,以及新的链表的虚拟头部开始
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        // 2-定义一个虚拟头结点，返回结果就是dummyHead.next
        ListNode dummyHead = new ListNode(-1);
        ListNode cur3 = dummyHead;
        // 3-开始遍历，比较两个指针遍历到的节点的值的大小:遍历结束的条件是两个链表都没有走完
        while (cur1!= null && cur2 != null){
            if(cur1.val <= cur2.val){
                cur3.next = cur1;
                cur1 = cur1.next;
            }else{
                cur3.next = cur2;
                cur2 = cur2.next;
            }
            cur3 = cur3.next;
        }
        // 4-如果有一个链表已经遍历结束，就直接拼接另一个链表
        if(cur1 == null){
            cur3.next = cur2;
        }else{
            cur3.next = cur1;
        }
        // 5-返回结果
        return dummyHead.next;
    }
}
